package org.example.myleet.p399;

import java.util.*;

public class Solution {
    /**
     * 2 ms
     */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        //图
        Map<List<String>, Double> graph = new HashMap<>();
        //出现过的节点
        Set<String> nodes = new HashSet<>();
        //初始化图，正向路径反向路径都加入图中，出现过的节点也缓存起来
        for (int i=0; i<equations.size(); i++) {
            List<String> path = equations.get(i);
            graph.put(path, values[i]);
            List<String> reversePath = new ArrayList<>(2);
            reversePath.add(path.get(1));
            reversePath.add(path.get(0));
            graph.put(reversePath, 1.0 / values[i]);
            nodes.add(path.get(0));
            nodes.add(path.get(1));
        }
        //输出结果
        double[] reply = new double[queries.size()];
        //从图中获得路径
        List<List<String>> paths = new ArrayList<>(graph.keySet());
        for (int i=0; i<queries.size(); i++) {
            //问题的起点和终点，根据起点在图中找出终点
            String start = queries.get(i).get(0);
            String end = queries.get(i).get(1);
            List<String> newPath = new ArrayList<>(2);
            newPath.add(start);
            newPath.add(end);
            if (graph.containsKey(newPath)) {
                //如果已经缓存了结果，直接给出
                reply[i] = graph.get(newPath);
                continue;
            }
            if (!nodes.contains(start) || !nodes.contains(end)) {
                //如果问题节点不在节点列表中，没有路径可以到达，直接-1
                reply[i] = -1.0;
                continue;
            }
            double result = -1.0;
            for (int j=0; j<paths.size(); j++) {
                if (paths.get(j).get(0).equals(start)) {
                    //找到起点的其中一条路径
                    if (start.equals(end)) {
                        //如果终点也是起点，直接给出答案
                        result = 1.0;
                        break;
                    }
                    //深度优先搜索寻找其中最近一个可能的结果
                    result = Math.max(result, dfs(graph, paths, paths.get(j).get(1), end, j, graph.get(paths.get(j)), new HashSet<>()));
                    if (result > -1.0) {
                        //找到可用路径，把这条路径的权重直接缓存到图中，更新路径集合
                        graph.put(newPath, result);
                        paths = new ArrayList<>(graph.keySet());
                        break;
                    }
                }
            }
            reply[i] = result;
        }
        return reply;
    }

    private double dfs(Map<List<String>, Double> graph, List<List<String>> paths, String lastEnd, String end, int i, double pathValue, Set<Integer> visited) {
        visited.add(i);
        if (i >= paths.size()) {
            //尽头
            return -1.0;
        }
        if (paths.get(i).get(1).equals(end)) {
            //找到了目标路径对应的权重了
            return pathValue;
        }
        for (int j=0; j<paths.size(); j++) {
            if (visited.contains(j)) {
                //已经访问过，不重复访问
                continue;
            }
            if (paths.get(j).get(0).equals(lastEnd)) {
                //上一个路径的终点是这个路径的起点，可以尝试继续走
                if (paths.get(j).get(0).equals(paths.get(i).get(1)) && paths.get(j).get(1).equals(paths.get(i).get(0))) {
                    //为了防止回头，对于这种反向路径作排除，防止死循环
                    continue;
                }
                //继续深度优先搜索往前走一个可能的路径
                double result = dfs(graph, paths, paths.get(j).get(1), end, j, pathValue * graph.get(paths.get(j)), visited);
                if (result > -1.0) {
                    return result;
                }
            }
        }
        //实在找不到了
        return -1.0;
    }
}
